/**
 * 合并两个有序链表
 * https://leetcode.cn/problems/merge-two-sorted-lists/description/
 * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
 * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
 *
 */
public class Solution21 {

    // 建议将 ListNode 定义为静态(static)内部类。
    // 因为它不需要访问外部类 Solution21 的实例成员，设为静态可以节省内存。
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode solution(ListNode list1, ListNode list2) {
        // 1. 使用一个“哨兵”或“哑”节点 (dummy node)，这可以极大简化处理链表头部的逻辑。
        //    变量名 `dummyHead` 比 `vf` 更具描述性。
        ListNode dummyHead = new ListNode(-1);

        // 2. 使用一个指针 `current` 来构建新链表，`p` 这个名字太通用了。
        ListNode current = dummyHead;

        // 3. 直接在循环中使用 list1 和 list2 作为指针，无需创建额外的 p1, p2。
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }

        // 4. 循环结束后，最多只有一个链表还有剩余节点。
        //    可以直接将新链表的末尾指向那个非空的链表，比用两个 if 判断更简洁。
        current.next = list1 != null ? list1 : list2;

        // 哨兵节点的下一个节点即为合并后链表的头节点
        return dummyHead.next;
    }
}